package com.base.dp;

import java.util.List;

public class WordBreak {

    public static void main(String[] args) {
        WordBreak wordBreak = new WordBreak();
        System.out.println(wordBreak.wordBreak2("leetcode",List.of("leet","code")));
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true; // 空字符串可以由字典中的单词拼接而成
        for (int i = 1; i <= s.length(); i++) {
            int p = 0;
            while(p<i && (!dp[p] || !wordDict.contains(s.substring(p,i)))){
                p++;
            }
            //一个都没有找到的情况下就不用再找了
            if(p!=i){
                dp[i]=dp[p];
            }

        }
        return dp[s.length()];

    }

    public boolean wordBreak2(String s,List<String> wordDict){
        if (s.isEmpty()){
            return true;
        }

        for (int i = 0; i < wordDict.size(); i++) {
            String current = wordDict.get(i);
            if (s.startsWith(current)){
                //找到了一个单词那么就，截取后面的待比较的字符串，继续执行
                if(wordBreak2(s.substring(current.length()),wordDict)){
                    return true;
                }
            }
        }
        return false;
    }
}
